#include<cstdio>
#include<algorithm>
#include<cmath>

#define N 1000

using namespace std;

struct node{
    int key;
    node *left, *right, *p;
};

struct tree{
    node *root;
};

void inorder_tree_walk(node *x){
    if (x != NULL) {
        inorder_tree_walk(x->left);
        printf("%d ", x->key);
        inorder_tree_walk(x->right);
    }
}

node* tree_search(node *x, int k){
    if (x == NULL || k == x->key)
        return x;
    if (k < x->key)
        return tree_search(x->left, k);
    else
        return tree_search(x->right, k);
}

node* iterative_tree_search(node *x, int k){
    while(x != NULL && k != x->key){
        if (k < x->key)
            x = x->left;
        else
            x = x->right;
    }
    return x;
}

node* tree_minimum(node *x){
    while(x->left != NULL)
        x = x->left;
    return x;
}

node* tree_maximum(node *x){
    while(x->right != NULL)
        x = x->right;
    return x;
}

node* tree_successor(node *x){
    if (x->right != NULL)
        return tree_minimum(x->right);
    node *y = x->p;
    while(y != NULL && x==y->right){
        x = y;
        y = y->p;
    }
    return y;
}

node* tree_predecessor(node *x){
    if (x->left!= NULL)
        return tree_maximum(x->left);
    node *y = x->p;
    while(y != NULL && x==y->left){
        x = y;
        y = y->p;
    }
    return y;
}

void tree_insert(tree *t, node *z){
    node *y = NULL;
    node *x = (t->root);
    while (x != NULL){
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->p = y;
    if (y == NULL)
        t->root = z;
    else if (z->key < y->key)
        y->left = z;
    else 
        y->right = z;
}

void transplant(tree *t, node *u, node *v){
    if (u->p == NULL)
        t->root = v;
    else if (u == u->p->left)
        u->p->left = v;
    else
        u->p->right = v;
    if (v != NULL)
        v->p = u->p;
}

void tree_delete(tree *t, node *z){
    if (z->left == NULL)
        transplant(t, z, z->right);
    else if (z->right == NULL)
        transplant(t, z, z->left);
    else {
        node *y = tree_minimum(z->right);
        if (y->p != z){
            transplant(t, y, y->right);
            y->right = z->right;
            y->right->p = y;
        }
        transplant(t, z, y);
        y->left = z->left;
        y->left->p = y;
    }
}

tree t;
int size;
node nodes[N];
int main(){
    t.root = NULL;
    size = 0;
    node u;
    u.p = u.left = u.right = NULL; 
    for(int i = 0; i < 10; i++){
        int j = rand() % 100;
        u.key = j;
        nodes[size++] = u;
        printf("*** Insert %d\n", u.key);
        tree_insert(&t, &nodes[size-1]);
    }
    for(int i = 0; i < 6; i++){
        printf("%d: ", i+1);
        inorder_tree_walk(t.root);
        printf("\n");
        switch(i){
            case 0:{
                node *v = tree_minimum(t.root);
                if (v == NULL)
                    printf("*** Null minimum\n");
                else
                    printf("*** Find minimum: %d\n", v->key);
                break;
                   }
            case 1:{
                int j = rand() % size;
                printf("*** Delete %d\n", nodes[j].key);
                tree_delete(&t, &nodes[j]);
                nodes[j] = nodes[size-1];
                size--;
                break;
                   }
            case 2:{
                int j = rand() % size;
                node *v = tree_successor(&nodes[j]);
                printf("*** Successor %d : ", nodes[j].key);
                if (v == NULL)
                    printf("NULL\n");
                else 
                    printf("%d\n", v->key); 
                break;
                   }
            case 3:{
                node *v = tree_maximum(t.root);
                if (v == NULL)
                    printf("*** Null maximum\n");
                else
                    printf("*** Find maximum: %d\n", v->key);
                break;
                   }
            case 4: {
                int j = rand() % size;
                node *v = tree_predecessor(&nodes[j]);
                printf("*** Prdedcessor %d : ", nodes[j].key);
                if (v == NULL)
                    printf("NULL\n");
                else
                    printf("%d\n", v->key);
                break;
                    }
        }
    }
    return 0;
}
